#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

string SEP = ",";     // 分隔符
string Null = "#";    // 空指针

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *next;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Code {
public:
    void stringBuilder(TreeNode *root, string &res) {
        if (root == nullptr) {
            // 节点为空
            res += Null;
            res += SEP;
            return;
        }
        // 正常序列化节点
        res += to_string(root->val);
        res += SEP;
        // 递归序列化左右节点
        stringBuilder(root->left, res);
        stringBuilder(root->right, res);
    }

    string serialize(TreeNode *root) {
        string res;
        if (root == nullptr)
            // 二叉树为空
            return "";
        stringBuilder(root, res);
        return res;
    }

    void split(const string &s, queue<string> &nodes, const string &token) {
        // 去除分隔符
        int length = s.size();
        int start = 0;
        int end = s.find(token);

        while (end != string::npos) {       // find没找到则返回npos标记
            nodes.push(s.substr(start, end - start));
            start = end + token.size();
            end = s.find(token, start);
        }
        if (start != length)
            nodes.push(s.substr(start));
    }

    TreeNode *getDeserilizedTree(queue<string> &nodes) {
        if (nodes.empty())
            return nullptr;
        string value = nodes.front();       // 获取前序第一个字符，为root节点
        nodes.pop();

        if (value == Null) return nullptr;

        TreeNode *root = new TreeNode(stoi(value)); 
        root->left = getDeserilizedTree(nodes);     // 递归获取left和right
        root->right = getDeserilizedTree(nodes);
        return root;
    }

    TreeNode *deserialize(string data) {
        queue<string> nodes;
        split(data, nodes, SEP);        // 去除分隔符
        return getDeserilizedTree(nodes);
    }

};

/*  寻找重复的子树--
    思路：
    step1: 遍历树，对每个阶段的树进行序列化
    step2: 比较hash_map中是否存在当前序列，如果存在说明出现了重复子树
    step3: 将重复子树记录下来输出
*/

class duplicateSubtrees {
public:
    vector<TreeNode *> findDuplicateSubtrees(TreeNode *root) {
        traverse(root);
        return res;
    }

    string traverse(TreeNode *root) {
        if (root == nullptr)
            return "#";

        string subTree = to_string(root->val) + "," + traverse(root->left) + "," + traverse(root->right);

        if (serials.count(subTree))
            // serials中含有subTree，则将其加入结果
            res.push_back(root);
        else
            // 否则将其加入serials
            serials[subTree]++;
    
        return subTree;
    }
private:
    unordered_map<string, int> serials;
    vector<TreeNode *> res;
};